1. Field of the Invention
The present invention relates to an image encoding/decoding method, an apparatus thereof, and a recording medium in which a program therefor is recorded, and more particularly, relates to an image encoding/decoding method, an apparatus thereof, and a recording medium in which a program therefor is recorded, according to Hybrid Vector Quantization (HVQ) system.
2. Description of Related Art
According to JPEG (Joint Photographic Expert Group) system, 8 times 8 pixel blocks are converted to DC (direct current) value and each coefficient value of from base to 63 times frequency by two dimensional DCT (discrete cosine transform), and information amount is reduced by quantizing the coefficient value in a different quantization width within no reduction of image quality utilizing frequency components of natural images which are gathered in a low frequency range, and then Huffman encoding is carried out.
According to HVQ system, which is a kind of mean value separation type block encoding same as JPEG, adaptive orthogonal transform (AOT) which is an intermediate system between a vector quantization and orthogonal transform encoding is used as a compression principle. AOT is a system in which the minimum number of non-orthogonal basis is selected from nests of the basis corresponding to a code book of vector quantization and the objective blocks become close to the desired and allowable error “Z”. According to the HVQ system, decoding is quickly carried because a decoding operation can be done in the form of integer. Natural images and artificial images (animation images, CG images) can be compressed in high image quality, because there are not mosquito and block noise, which are particularly generated in JPEG, and false contour, which is particularly generated in GIF. The invention relates to a method for further improving the image quality and for carrying out the coding operation at a higher speed in the HVQ system.
The applicants of the invention have proposed an image encoding/decoding method in accordance with the HVQ system utilizing self-similarity of images in Japanese Patent Application No. 189239/98. The contents of such proposal will be explained as follows. In the disclosure, a sign <a> means vector “a” or block “a”, a sign ∥a∥ means norm of the vector “a”, and a sign <a·b> means inner product of vectors a and b. Further, vectors and blocks in drawings and [numbers] are represented by block letters.
FIG. 1 is a block diagram showing a conventional image encoder. In FIG. 1, 11 is an original image memory for storing an original image data, 12 is a DC value production unit for seeking a block average (DC) value per each pixel block (4 times 4 pixel) of the original image data, 13 is a differential PCM encoding unit (DPCM) for carrying out a differential predict encoding per each DC value, 14 is inverse DPCM encoding unit for decoding each DC value from the differential PCM encoding, 15 is a DC image memory for storing a decoded DC image, 16 is a DC nest production unit for cutting off the DC nest of a desired size from a part of the DC image, and 17 is a DC nest memory for storing the DC nest.
Further, 18 is a subtractor for separating a corresponding decoding DC value “DCJ” from a target image block <RJ> to be encoded, 19 is a differential vector buffer for storing a differential vector <dJ> which is DC separated, 20 is an extracted block buffer for storing a base extraction block <Ui> of 4 times 4 pixels which is down-sampled from the DC nest, 21 is an equilibrator for seeking a block mean value ai of the base extraction block <Ui>, 22 is a subtractor for separating the block means value ai from the base extraction block <Ui>, 23 is an extracted vector buffer for storing the base extraction block <Ui> which is separated by the mean value, 24 is an adaptive orthogonal transform (AOT) processing unit for producing an orthogonal basis αk<uk′> (k=1˜m) to search the DC nest to make the differential vector <dj> closer to the allowable error Z, where a square norm ∥dj∥2 of the differential vector is over the allowable error Z, 25 is a coefficient transform unit for seeking an expanding square coefficient βk which is multiplied by a non-orthogonal basis vector <uk> (k=1˜m) per the produced orthogonal basis αk <uk′> (k=1˜m) to produce an equivalent non-orthogonal basis βk <uk> (k=1˜m), and 26 is an encoding unit by Huff man coding, run length coding or fixed length coding system for the compression encoding of information such as DPCM encoding of the DC value or the non-orthogonal basis βk<uk>.
In the DC value production unit 12, the block mean value of 4 times 4 pixels is provided in which the first decimal place is rounded off or down. In the DPCM 13, where the DC value of row J and column T is shown by the DCJ, I, a predictive value DCJ, I′ of the DCJ,I is provided by the formula, DCJ, I′=(DCJ, I−1+DCJ−1, I)/2, and its predictive error (Δ DCJ, I=DCJ, I−DCJ, I′) is linear-quantized by a quantization coefficient Q(Z) and is output. The quantization coefficient Q(Z) corresponds to the allowable error Z and is variable within the range of 1 to 8 according to the allowable error Z.
In the DC nest production unit 16, the DC nest is prepared by copying the range of vertical 39×horizontal 71 from the DC image. It is preferred that the DC nest includes more alternating current components because it is used as a code book. Therefore, it is prepared by copying such the range that the sum of absolute values of difference between the DC values adjacent to each other in a plurality of the extracted ranges become maximum.
In making down-samples of the base extraction block <Ui>, a vertex per one DC value in vertical and horizontal section is set to (px, py) ∈ [0, 63]×[0, 31] and a distance of its sub-samples is set to 4 kinds of (sx, sy) ∈ {(1, 1), (1, 2), (2, 1), (2, 2)}. Accordingly, the total numbers of the base extraction blocks <Ui> are N(=8192) and are referred by an index counter “i” from the AOT 24. Behavior of conventional adaptive orthogonal transform processing unit 24 will be explained below.
FIG. 2 is a flow chart of conventional adaptive orthogonal transform processing and FIG. 3 is an image drawing of the processing. In FIG. 2, it is input in the processing that the square norm ∥dj∥2 of the differential vector is more than Z. In step S121, the square norm ∥dj∥2 of the differential vector is set in a resister E. A basis number counter is initialized to k=1. In step S122, much value (e.g. 100,000) is set in a minimum value holding resister E′. In step S123, an index counter of the base extraction block<Ui> is initialized to i=0. By these steps, the initial address and distance of sub-samples in the DC nest are set to (px, py)=(0, 0) and (sx, sy)=(1, 1), respectively.
In step S124, the base extraction vector <ui> is produced by separating the block mean value ai from the base extraction blocks <Ui>. Since the operation or calculation is carried out under the accuracy of integer level, any value of first decimal place in the block mean value ai is rounded off or down. In step S125, the base extraction vector <ui> is subjected to orthogonal transform processing to be converted to the orthogonal basis vector <uk′>, if necessary (k>1).
FIGS. 3(A) and (B) are image drawings of the orthogonal transform processing. In FIG. 3(A), the first base extraction vector <u1> can be the first basis vector <u1′> as it is.
Then, the second base extraction vector <u2> is subjected to orthogonal transform processing to be converted to the second basis vector <u2′> in accordance with the following method. That is, a shadow of the second base extraction vector <u2> projected on the first basis vector <u1′> is represented by the formula (1).
                    [                  Numeral          ⁢                                          ⁢          1                ]                                                                                                                                                                        u                    2                                                                    ⁢                                                                  ⁢                cos                ⁢                                                                  ⁢                θ                            =                                                〈                                                            u                      1                      ′                                        ·                                                                                  ⁢                                          u                      2                                                        〉                                                                                        u                    1                    ′                                                                                                                                                                                                      ∵                                  〈                                                            u                      1                      ′                                        ·                                                                                  ⁢                                          u                      2                                                        〉                                            =                                                                                      u                    1                    ′                                                                    ⁢                                                                        u                    2                                                                    ⁢                                                                  ⁢                cos                ⁢                                                                  ⁢                θ                                                                        (        1        )            
Accordingly, the second orthogonal vector <u2′> is obtained by subtracting the vector of the projected shadow from the second base extraction vector <u2>.
                    [                  Numeral          ⁢                                          ⁢          2                ]                                                                      u          2          ′                =                              u            2                    -                                                    〈                                                      u                    1                    ′                                    ⁢                                                                          ⁢                                      u                    2                                                  〉                                                                              u                  1                  ′                                                                      ⁢                                          u                1                ′                                                                              u                  1                  ′                                                                                                        (        2        )            
In FIG. 3(B), the third base extraction vector <u3> is subjected to orthogonal transform processing to the first basis vector <u1′> and the second basis vector <u2′>.
FIG. 3 is three-dimensionally drawn. The third base extraction vector <u3> is subjected to orthogonal transform processing to the first basis vector <u1′> to obtain an intermediate orthogonal vector <u3″>.
                    [                  Numeral          ⁢                                          ⁢          3                ]                                                                      u          3          ″                =                              u            3                    -                                                    〈                                                      u                    1                    ′                                    ·                                                                          ⁢                                      u                    3                                                  〉                                                                                                    u                    1                    ′                                                                    2                                      ⁢                          u              1              ′                                                          (        3        )            
Further, the intermediate orthogonal vector <u3″> is subjected to orthogonal transform processing to the second basis vector <u2′> to obtain the third basis vector <U3′>.
                    [                  Numeral          ⁢                                          ⁢          4                ]                                                                      u          3          ′                =                              u            3            ″                    -                                                    〈                                                      u                    2                    ′                                    ·                                                                          ⁢                                      u                    3                    ″                                                  〉                                                                                                    u                    2                    ′                                                                    2                                      ⁢                          u              2              ′                                                          (        4        )                                                          ⁢                  =                                    (                                                u                  3                                -                                                                            〈                                                                        u                          1                          ′                                                ·                                                                                                  ⁢                                                  u                          3                                                                    〉                                                                                                                                        u                          1                          ′                                                                                            2                                                        ⁢                                      u                    1                    ′                                                              )                        -                                                            〈                                                            (                                                                        u                          3                                                -                                                                                                            〈                                                                                                u                                  1                                  ′                                                                ·                                                                                                                                  ⁢                                                                  u                                  3                                                                                            〉                                                                                                                                                                                        u                                  1                                  ′                                                                                                                            2                                                                                ⁢                                                      u                            1                            ′                                                                                              )                                        ⁢                                                                                  ·                                                                                  ⁢                                          u                      2                      ′                                                        〉                                                                                                                u                      2                      ′                                                                            2                                            ⁢                              u                2                ′                                                                                                                                  ⁢                  =                                    u              3                        -                                                            〈                                                            u                      1                      ′                                        ·                                                                                  ⁢                                          u                      3                                                        〉                                                                                                                u                      1                      ′                                                                            2                                            ⁢                              u                1                ′                                      -                                                            〈                                                            u                      2                      ′                                        ·                                                                                  ⁢                                          u                      3                                                        〉                                                                                                                u                      2                      ′                                                                            2                                            ⁢                              u                2                ′                                                                                    
Turning to FIG. 2, in step S126, a scalar coefficient αi is calculated using the orthogonal vector <ui′> so that a distance with the differential vector <dk> (at first<dj>) becomes minimum.
FIG. 3(C) is an image drawing of the orthogonal transform processing. In FIG. 3(C), where a differential vector represented by <dk> is subjected to approximation, a square norm thereof (ei=∥<dk>−αi<ui′>∥2) is minimum when the product of the orthogonal vector <ui′> and the scalar coefficient αi is diagonal with the differential vector {<dk>−αi<ui′>} as shown in FIG. 3(C) (inner product=0). Accordingly, the scalar coefficient αi is obtained by the formula (5).
                    [                  Numeral          ⁢                                          ⁢          5                ]                                                                                                                〈                                                      α                    i                                    ⁢                                                            u                      i                      ′                                        ⁢                                                                                  ·                                                                                  ⁢                                          (                                                                        d                          k                                                -                                                                              α                            i                                                    ⁢                                                      u                            i                            ′                                                                                              )                                                                      〉                            =              0                                                                                                                                                                          α                    i                                    ⁢                                      〈                                                                  u                        i                        ′                                            ⁢                                                                                          ·                                                                                          ⁢                                              d                        k                                                              〉                                                  -                                                      α                    i                    2                                    ⁢                                      〈                                                                  u                        i                        ′                                            ⁢                                                                                          ·                                                                                          ⁢                                              u                        i                        ′                                                              〉                                                              =              0                                                          (                  5          ⁢                      -                    ⁢          1                )                                          α          i                =                              〈                                          d                k                            ⁢                                                          ·                                                          ⁢                              u                i                ′                                      〉                                                                            u                i                ′                                                    2                                              (                  5          ⁢                      -                    ⁢          2                )            
It is shown in the drawing that the differential vector <dk> (k=0) is subjected to approximation to other first base extraction vector <uj′>. The first base extraction vector <uj′> is shown by the image drawing because it can take optional directions.
Turning to FIG. 2, in step S127, a square norm (ei) of error vector is obtained by the formula (6) after the differential vector <dk> (k=0) is subjected to approximation to the base extraction vector αi<uj′>.
                    [                  Numeral          ⁢                                          ⁢          6                ]                                                                      e          i                =                                                                        d                k                            -                                                α                  i                                ⁢                                  u                  i                  ′                                                                          2                                    (        6        )                                                          ⁢                  =                                                                                      d                  k                                                            2                        -                          2              ⁢                                                          ⁢                              α                i                            ⁢                              〈                                                      d                    k                                    ·                                                                          ⁢                                      u                    i                    ′                                                  〉                                      +                                          α                i                2                            ⁢                                                                                      u                    i                    ′                                                                    2                                                                                                                                  ⁢                  =                                                                                      d                  k                                                            2                        -                          2              ⁢                                                                    〈                                                                  d                        k                                            ·                                                                                          ⁢                                              u                        i                        ′                                                              〉                                    2                                                                                                                u                      i                      ′                                                                            2                                                      +                                                                                〈                                                                  d                        k                                            ·                                                                                          ⁢                                              u                        i                        ′                                                              〉                                    2                                                                                                                u                      i                      ′                                                                            4                                            ⁢                                                                                      u                    i                    ′                                                                    2                                                                                                                                  ⁢                  =                                                                                      d                  k                                                            2                        -                                                            〈                                                            d                      k                                        ·                                                                                  ⁢                                          u                      i                      ′                                                        〉                                2                                                                                                    u                    i                    ′                                                                    2                                                                                                                                  ⁢                  =                      E            -                                                            〈                                                            d                      k                                        ·                                                                                  ⁢                                          u                      i                      ′                                                        〉                                2                                                                                                    u                    i                    ′                                                                    2                                                                                    
In step S128 of FIG. 2, it is judged whether ei is less than E′ or not. If ei is less than E′, content of E′ is renewal in step S129 and the information regarding αi, <ui′>, <ui>, etc. at the time is held in an arrangement [αk], [uk′], [uk], etc. If ei is not less than E′, the processing in step S129 is skipped.
In step S130, one (1) is added to the counter i, and in step S131, it is judged whether i is not less than N (=8192) or not. If i is less than N, turning to step 124 and the same processing is carried out with respect to next base extraction vector <ui>.
The processing is repeated and when it is judged in step S131 that i is not less than N, all base extraction vectors <ui> have been completely tried. At the time, the register E′ holds the minimum square norm ei.
It is judged in step S132 whether E′ is not more than Z or not. If E′ is more than Z, it is treated as E=E′ in step S133. That is, the square norm of the differential vector is renewal. In step S134, one (1) is added to the counter k, turning to step S122. If E′ is not more than Z, this processing is skipped. Thus, the orthogonal basis αk<uk′>(k=1˜m) to approximate the difference of the first differential vector <dj> to the allowable error Z is obtained.
However, the block mean value ai of the base extraction block <Ui> has been rounded off or down in the conventional methods and therefore, improvement of image quality is limited. Why the conventional methods are inconvenient will be explained according to FIG. 4.
FIG. 4 is an image drawing of mean value separation processing. A relationship of base extraction block <Ui> (vertical axis) with the pixel value of certain row (horizontal axis) is shown in FIG. 4(a). An actual pixel value is a block mean value of 16 pixels, but the block mean value of 4 pixels will be used to simplify the explanation herein. In FIG. 14(a), each pixel value is 5, 2, 4, and 3 and its mean value ai is 3.5. when the first decimal place is round down, the block mean value ai of the base extraction block <ui> is 0.5 as shown in FIG. 4(b). In FIG. 4(c), if the basis vector βk uk< is added to the DC value DCJ of the decoded block, the DC component (ai=0.5) is overlapped on the target block <Rj>. In case that the number of basis is plural, the DC value is overlapped on the DCJ by various values in the range of 0<ai<1, and as a result, certain noise is over lapped per each block in the decoded image, whereby image quality is not improved. This disadvantage also occurs in case that the first decimal place is rounded off or up.
According to the conventional AOT processing, much operations and much time are required, because all of the base extraction vectors <ui> must be subjected to orthogonal processing to the preceding base vectors <uk′>.